package 代码记录.剑指offer错题本;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

/**
 * @author zx
 * @create 2022-06-04 22:01
 */
public class 二叉树中和为某一值的路径_34 {
    /**
     * 说是回溯算法,但是回溯细节没理解
     */
    List<List<Integer>> res = new ArrayList<List<Integer>>();
    Deque<Integer> path = new ArrayDeque<>();
    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        helper(root,targetSum);
        return res;
    }
    private void helper(TreeNode root,int target){
        if(root == null){
            return;
        }
        path.offerLast(root.val);
        target -= root.val;
        if(root.left == null && root.right == null){
            if(target == 0){
                //满足条件的path添加到路径中
                res.add(new ArrayList<Integer>(path));
            }
        }
        helper(root.left,target);
        helper(root.right,target);
        path.pollLast();
    }

}
class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}